package STO_16_11;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Solution {
	public int[] divingBoard(int shorter, int longer, int k) {
		if (k == 0) {
			return new int[] {};
		}
		int[] nums = { shorter, longer };
		List<Integer> path = new LinkedList<Integer>();
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		TB(nums, 0, k, path, res);
		Set<Integer> all = new HashSet<Integer>();
		for (List<Integer> list : res) {
			int sum = 0;
			for (Integer num : list) {
				sum += num;
			}
			all.add(sum);
		}
		int all_size = all.size();
		int[] ret = new int[all_size];
		int i = 0;
		for (Integer integer : all) {
			ret[i++] = integer;
		}

		return ret;

	}

	private void TB(int[] nums, int i, int k, List<Integer> path, List<List<Integer>> res) {
		// TODO Auto-generated method stub
		if (i == k) {
			res.add(new LinkedList<Integer>(path));
			return;
		}
		for (int j = 0; j < nums.length; j++) {
			path.add(nums[j]);
			TB(nums, i + 1, k, path, res);
			path.remove(path.size() - 1);
		}

	}

	public int[] divingBoard_math(int shorter, int longer, int k) {
		if (k == 0) {
			return new int[] {};
		}
		if (shorter == longer) {
			return new int[] { shorter * k };
		}
		int[] lengths = new int[k + 1];
		for (int i = 0; i <= k; i++) {
			lengths[i] = shorter * (k - i) + longer * i;
		}
		return lengths;
	}
}
